//https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
package codeRandomThoughts.Test28找出字符串中第一个匹配项的下标;

import java.util.Arrays;

/**
 * 第二次写KMP 这次看能不能多理解一点
 * KMP的重点在于指针的不断往回跳跃
 * for循环里面的第一步就是让指针一直跳,检测下一步能不能匹配上
 * 如果实在匹配不上,那直接重开了,也就是说回到-1的位置
 */
public class Solution3 {
    public static int strStr(String haystack, String needle) {
        //转换成char数组 效率高些
        char[] str = haystack.toCharArray();
        char[] p = needle.toCharArray();
        int[] next = getNextFromPattern(needle);

        //定义两个指针 一个指向字符串str 一个指向模式串p
        int i = -1;//指向第一个字符之前
        int j = -1;//指向p中第一个字符之前
        for (i = -1; i < str.length - 1; i++) {

            //如果一直找不到合适的 那就等j跳到开头了停止 也就是-1
            while (j > -1 && str[i + 1] != p[j + 1]) {
                j = next[j];
            }

            if (str[i + 1] == p[j + 1]) {
                //如果指向的下一个字符相同
                j++;
            }

            //如果j右移到了模式串的终点,代表能够查找到模式串,反转模式串初始位置
            if (j == (p.length - 1)) {
                //此时i还没有++
                return i - p.length + 2;
            }
        }

        //没有找到模式串
        return -1;
    }

    /**
     * 感觉这个代码写的是最好的一次了
     *
     * @param needle 需要匹配的模式串
     * @return next数组, 下标从0开始
     */
    public static int[] getNextFromPattern(String needle) {
        //把模式串转成char数组,效率高些
        char[] pattern = needle.toCharArray();

        //我们的next下标从0开始
        int[] next = new int[pattern.length];

        //从0开始就得初始化成-1
        next[0] = -1;
        int prefixEnd = 0;
        int postfixEnd = 0;
        for (int i = 0; i < pattern.length - 1; i++) {
            //指向当前的前缀末尾和后缀末尾字符所在的位置
            prefixEnd = next[i];
            postfixEnd = i;
            //用预测写法
            while (prefixEnd > -1 && pattern[prefixEnd + 1] != pattern[postfixEnd + 1]) {
                //改变前缀末尾 往回跳
                prefixEnd = next[prefixEnd];
            }

            if (pattern[prefixEnd + 1] == pattern[postfixEnd + 1]) {
                //如果下一项前缀末尾和后缀末尾相等
                next[i + 1] = prefixEnd + 1;
            } else {
                //匹配不上就是-1
                next[i + 1] = -1;
            }
        }

        return next;
    }


    public static void main(String[] args) {
        String str = "aadascvdsv";
        String p = "aabaabaaab";
        int[] next = getNextFromPattern(p);
        System.out.println(Arrays.toString(next));
    }
}
